package main

import (
	"fmt"
	. "local/algorithm/util"
)

/**
分析:
由于两个链表中数字是倒序存储，对数字相加可以翻译为从左向右遍历相加，每位相加后的值为sum(sum=v1+v2+carry)需要注意的是进位处理，用carry存储，默认值为0，每次向右进位前carry=carry/10
对于返回值，我们肯定是返回头结点，于是头结点的位置需要保存，用另外一个指针进行迭代遍历
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	carry := 0
	sum := 0
	dn := &ListNode{}
	cur := dn
	for {
		if carry == 0 && l1 == nil && l2 == nil {
			break
		}
		sum += carry
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		node := &ListNode{Val: sum % 10}
		carry = sum / 10
		cur.Next = node
		cur = cur.Next
	}
	return dn.Next
}

func main() {
	l1 := GenerateLinkedList([]int{2,4,3})
	l2 := GenerateLinkedList([]int{5,6,4})
	l3 := addTwoNumbers(l1, l2)
	fmt.Println(l3)
}
